The use of overlay networks, also called virtual networks, is gaining popularity in data centers and other multiple tenant data storage environments for its ability to decouple physical and virtual networks and allow one physical network infrastructure to provide virtual networks for multiple tenants. In an overlay network, the separation of tenants is hidden from the underlying physical infrastructure. Thus, the underlying transport network does not need to know about tenancy separation to forward traffic correctly. To enable individual tenants to utilize this environment, the resource provider for the data center, for example, a cloud service provider (CSP), sets up a respective VPN gateway for each tenant to provide access to each respective tenant. This infrastructure is problematic because per-tenant VPN gateway deployment utilizes network resources and increases the management overhead for the infrastructure of the data center as a whole. Thus, both capital and operational expenses can increase dramatically as the number of tenants of the multi-tenant data storage environment expands.